package 归并;

public class Solution {
    public static int[] tmp;
    public static int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public static void mergeSort(int[] nums, int left, int right){
        if(left>=right){
            return;
        }
        int mid= (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //合并两个有序数组
        int i=0;
        int cur1=left;
        int cur2=mid+1;
        while(cur1<=mid&&cur2<=right){
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        }

        while(cur1<=mid){
            tmp[i++]=nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=nums[cur2++];
        }
        //还原数组
        for(int k=left;k<=right;k++){
            nums[k]=tmp[k-left];
        }
    }

    public static void main(String[] args) {
        int nums[]={5,4,3,7,9,10,1};
        sortArray(nums);
    }
}
